{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Deletions on a String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming #string-matching #hash-function #rolling-hash"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划 #字符串匹配 #哈希函数 #滚动哈希"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: deleteString"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #对字母串可执行的最大删除数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个仅由小写英文字母组成的字符串 <code>s</code> 。在一步操作中，你可以：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>删除 <strong>整个字符串</strong> <code>s</code> ，或者</li>\n",
    "\t<li>对于满足&nbsp;<code>1 &lt;= i &lt;= s.length / 2</code> 的任意 <code>i</code> ，如果 <code>s</code> 中的 <strong>前</strong> <code>i</code> 个字母和接下来的 <code>i</code> 个字母 <strong>相等</strong> ，删除 <strong>前</strong> <code>i</code> 个字母。</li>\n",
    "</ul>\n",
    "\n",
    "<p>例如，如果 <code>s = \"ababc\"</code> ，那么在一步操作中，你可以删除 <code>s</code> 的前两个字母得到 <code>\"abc\"</code> ，因为 <code>s</code> 的前两个字母和接下来的两个字母都等于 <code>\"ab\"</code> 。</p>\n",
    "\n",
    "<p>返回删除 <code>s</code> 所需的最大操作数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abcabcdabc\"\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>\n",
    "- 删除前 3 个字母（\"abc\"），因为它们和接下来 3 个字母相等。现在，s = \"abcdabc\"。\n",
    "- 删除全部字母。\n",
    "一共用了 2 步操作，所以返回 2 。可以证明 2 是所需的最大操作数。\n",
    "注意，在第二步操作中无法再次删除 \"abc\" ，因为 \"abc\" 的下一次出现并不是位于接下来的 3 个字母。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"aaabaab\"\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>\n",
    "- 删除第一个字母（\"a\"），因为它和接下来的字母相等。现在，s = \"aabaab\"。\n",
    "- 删除前 3 个字母（\"aab\"），因为它们和接下来 3 个字母相等。现在，s = \"aab\"。 \n",
    "- 删除第一个字母（\"a\"），因为它和接下来的字母相等。现在，s = \"ab\"。\n",
    "- 删除全部字母。\n",
    "一共用了 4 步操作，所以返回 4 。可以证明 4 是所需的最大操作数。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"aaaaa\"\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>在每一步操作中，都可以仅删除 s 的第一个字母。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 4000</code></li>\n",
    "\t<li><code>s</code> 仅由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-deletions-on-a-string](https://leetcode.cn/problems/maximum-deletions-on-a-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-deletions-on-a-string](https://leetcode.cn/problems/maximum-deletions-on-a-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abcabcdabc\"', '\"aaabaab\"', '\"aaaaa\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if len(set(s)) == 1: return n\n",
    "        f = [1] * n\n",
    "        for i in range(n-2,-1,-1):\n",
    "            for j in range(1,(n-i)//2+1):\n",
    "                if s[i:i+j] == s[i+j:i+j*2]:\n",
    "                    f[i]=max(f[i],1+f[i+j])\n",
    "        return f[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        # lcp = [[0] * (n+1) for _ in range(n+1)]\n",
    "        # for i in range(n-1, -1, -1):\n",
    "        #     for j in range(n-1, -1, -1):\n",
    "        #         if s[i] == s[j]:\n",
    "        #             lcp[i][j] = lcp[i+1][j+1] + 1\n",
    "        \n",
    "        f = [0] * n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(1, (n-i)//2+1):\n",
    "                # if lcp[i][i+j] >= j:\n",
    "                if s[i:i+j] == s[i+j:i+2*j]:\n",
    "                    f[i] = max(f[i], f[i+j])\n",
    "            f[i] += 1\n",
    "        return f[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        f = [-10 ** 8] * (n + 1)\n",
    "        f[0] = 0\n",
    "        for i in range(n):\n",
    "            l = 1\n",
    "            f[n] = max(f[n], f[i] + 1)\n",
    "            while i + 2 * l <= n:\n",
    "                if s[i: i + l] == s[i + l: i + l + l]:\n",
    "                    f[i + l] = max(f[i + l], f[i] + 1)\n",
    "                    # print(i + l, f[i + 1], i, s[i:i + l])\n",
    "                l += 1\n",
    "        return f[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [-inf] * (n + 1)\n",
    "        dp[0] = 0\n",
    "        ans = 1\n",
    "        for i in range(n):\n",
    "            # 长度为d  [i-d+1,i] [i+1,i+d] 相等\n",
    "            # 左侧长度 i+1, 右侧长度 n-i-1\n",
    "            for d in range(1, min(i + 1, n - i - 1) + 1):\n",
    "                if s[i - d + 1: i + 1] == s[i + 1: i + 1 + d]:\n",
    "                    dp[i + 1] = max(dp[i + 1], dp[i - d + 1] + 1)\n",
    "            if i < n:\n",
    "                ans = max(ans, dp[i + 1] + 1)\n",
    "            else:\n",
    "                ans = max(ans, dp[i + 1])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        N = len(s)\n",
    "        ordA = ord('a')\n",
    "        states = [1]*N\n",
    "        for off in range(len(s)-1, -1, -1):\n",
    "            _len = (N-off)>>1\n",
    "            for l in range(1, _len+1):\n",
    "                if s[off:off+l] == s[off+l:off+l*2]:\n",
    "                    states[off] = max(states[off], states[off+l] + 1)\n",
    "        # print(states, blockCs, blockNs)\n",
    "        return states[0]\n",
    "\n",
    "            # nB - 1 - idx - 1 = idx - x\n",
    "\n",
    "            # nBlocks - 1 - idxBlocks - 1 = idxBlocks - x\n",
    "            # x = idxBlocks +2 + idxBlocks - nBlocks > 0\n",
    "            # idxBlocks*2 + 2> nBlocks\n",
    "        # R[n] = R[m] + 1 if s[n...m-1] == s[m...m+m-n-1]\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        # 定义f[i]表示删除后缀s[i:]所需要的最大操作数\n",
    "        # f[i] = f[i+j:] if s[i: i + j] == s[i + j: i + 2j]\n",
    "        # f[i] = 1\n",
    "        # 取max\n",
    "        # 但是这个s[i: i + j] == s[i + j: i + 2j]是否相等应该如何计算呢？\n",
    "        n = len(s)\n",
    "        f = [1] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(1, (n - i) // 2 + 1):\n",
    "                if s[i: i + j] == s[i + j: i + 2 * j]:\n",
    "                    f[i] = max(f[i], f[i + j] + 1)\n",
    "        return f[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "@可爱抱抱呀\n",
    "执行用时：4500 ms, 在所有 Python3 提交中击败了57.93%的用户\n",
    "内存消耗：15.2 MB, 在所有 Python3 提交中击败了85.90%的用户\n",
    "2022年10月4日 9:45\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        ans=[1]*n\n",
    "        for i in range(n-2,-1,-1):\n",
    "            for j in range(1,(n-i)//2+1):\n",
    "                if s[i:i+j]==s[i+j:i+j*2]:\n",
    "                    ans[i]=max(ans[i],1+ans[i+j])\n",
    "        return ans[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if min(s) == max(s):\n",
    "            return n\n",
    "        f = [-10 ** 8] * (n + 1)\n",
    "        f[0] = 0\n",
    "        for i in range(n):\n",
    "            l = 1\n",
    "            f[n] = max(f[n], f[i] + 1)\n",
    "            while i + 2 * l <= n:\n",
    "                if s[i: i + l] == s[i + l: i + l + l]:\n",
    "                    f[i + l] = max(f[i + l], f[i] + 1)\n",
    "                    # print(i + l, f[i + 1], i, s[i:i + l])\n",
    "                l += 1\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        f = [0] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(1, (n - i) // 2 + 1):\n",
    "                if s[i:i+j]==s[i+j:i+2*j]:  # 说明 s[i:i+j] == s[i+j:i+2*j]\n",
    "                    f[i] = max(f[i], f[i + j])\n",
    "            f[i] += 1\n",
    "        return f[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        \n",
    "        n=len(s)\n",
    "        dp=[1]*n\n",
    "\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(1,n):\n",
    "                if i+2*j>n:\n",
    "                    break\n",
    "                if s[i:i+j]==s[i+j:i+2*j]:\n",
    "                    dp[i]=max(dp[i],dp[i+j]+1)\n",
    "\n",
    "        \n",
    "        return dp[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [1]*n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for t in range(1, n):\n",
    "                if i + 2 * t > n: break\n",
    "                if s[i:i+t] == s[i+t:i+2*t]:\n",
    "                    dp[i] = max(dp[i], 1 + dp[i+t])\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        if len(set(s))==1:return n\n",
    "        def prefix(s):\n",
    "            n = len(s)\n",
    "            pi = [0] * n\n",
    "            j = 0\n",
    "            for i in range(1, n):\n",
    "                while j > 0 and s[i] != s[j]:\n",
    "                    j = pi[j - 1]  # j指向之前位置，s[i]与s[j]继续比较\n",
    "                if s[i] == s[j]:  # s[i]与s[j]相等，j+1，指向后一位\n",
    "                    j += 1\n",
    "                pi[i] = j\n",
    "            return pi\n",
    "        f=[1]*n\n",
    "        for i in range(n-2,-1,-1):\n",
    "            pi = prefix(s[i:])\n",
    "            for j in range(1,len(pi)):\n",
    "                if pi[j]*2==j+1:\n",
    "                    f[i]=max(f[i],f[i+pi[j]]+1)\n",
    "        return f[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        if len(set(s))==1:return n\n",
    "        def prefix(s):\n",
    "            n = len(s)\n",
    "            pi = [0] * n\n",
    "            j = 0\n",
    "            for i in range(1, n):\n",
    "                while j > 0 and s[i] != s[j]:\n",
    "                    j = pi[j - 1]  # j指向之前位置，s[i]与s[j]继续比较\n",
    "                if s[i] == s[j]:  # s[i]与s[j]相等，j+1，指向后一位\n",
    "                    j += 1\n",
    "                pi[i] = j\n",
    "            return pi\n",
    "        f=[1]*n\n",
    "        for i in range(n-2,-1,-1):\n",
    "            pi = prefix(s[i:])\n",
    "            for j in range(1,len(pi)):\n",
    "                if pi[j]*2==j+1:\n",
    "                    f[i]=max(f[i],f[i+pi[j]]+1)\n",
    "        return f[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if len(set(s)) == 1:\n",
    "            return n\n",
    "        @cache\n",
    "        def dp(i):\n",
    "            if i == len(s): # 递归出口，如果整个字符串都被删完了，那么就返回0，因为此时不能再进行删除了\n",
    "                return 0 \n",
    "            res = 1 # res初值设为1，是因为我最少都需要一次删除的操作，才能把整个字符串删完\n",
    "            for j in range(i+1, n):\n",
    "                t = j - i # t表示要删除的长度\n",
    "                if i + 2 * t > n: break \n",
    "                if s[i:i+t] == s[i+t:i+2*t]: # 如果删除的操作合法\n",
    "                    res = max(res, 1 + dp(i+t)) # 更新最大值，1+dp[i+t]，表示当前的删除操作次数1，和后续字符串操作次数的和\n",
    "            return res\n",
    "        return dp(0)\n",
    "\n",
    "        \n",
    "        lcp = [[0]*(n+1) for _ in range(n+1)]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if s[i]!=s[j]:\n",
    "                    lcp[i][j] = 0\n",
    "                else:\n",
    "                    lcp[i][j] = lcp[i+1][j+1] + 1\n",
    "        \n",
    "\n",
    "        dp = [1] * (n)\n",
    "        \n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(i+1,n):\n",
    "                t = j-i\n",
    "                if i+2*t >n:break\n",
    "                if lcp[i][i+t]>=t:\n",
    "                    dp[i] = max(dp[i],1+dp[i+t])\n",
    "        return dp[0]\n",
    "        # return dp(0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "\n",
    "        @lru_cache(maxsize=None)\n",
    "        def dfs(i):\n",
    "            if i >= len(s):\n",
    "                return 0\n",
    "            result = 1\n",
    "            for j in range(i+1, i+(len(s)-i)//2+1):\n",
    "                if s[i:j] == s[j:j+j-i]:\n",
    "                    result = max(result, 1+dfs(j))\n",
    "            return result\n",
    "        \n",
    "        return dfs(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        def prefix_function(s: str) -> List[int]:\n",
    "            n = len(s)\n",
    "            nxt = [0] * n\n",
    "            res = []\n",
    "            for i in range(1, n):\n",
    "                j = nxt[i - 1]\n",
    "                while j > 0 and s[j] != s[i]:\n",
    "                    j = nxt[j - 1]\n",
    "                if s[j] == s[i]:\n",
    "                    j += 1\n",
    "                nxt[i] = j\n",
    "                if i + 1 == 2 * j:\n",
    "                    res.append((i + 1) // 2)\n",
    "            return res\n",
    "        @cache\n",
    "        def dfs(i: int) -> int:\n",
    "            res = 0\n",
    "            for j in prefix_function(s[i : ]):\n",
    "                res = max(res, dfs(i + j) + 1)\n",
    "            return res\n",
    "        # res = prefix_function(s)\n",
    "        # while res != -1:\n",
    "        #     ans += 1\n",
    "        #     print(res)\n",
    "        #     s = s[res : ]\n",
    "        #     res = prefix_function(s)\n",
    "        return dfs(0) + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            \n",
    "            res = 1\n",
    "            for j in range(i + 1, n):\n",
    "                if j - i > n - j:\n",
    "                    break\n",
    "                if s[i:j] == s[j:j + j - i]:\n",
    "                    res = max(res, 1 + dfs(j))\n",
    "            return res\n",
    "\n",
    "        ans = dfs(0)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i >= j:\n",
    "                return 1\n",
    "            res = 1\n",
    "            for k in range(1, (j - i + 1) // 2 + 1):\n",
    "                # print(i, j, s[i:i + k], s[i + k:i + k + k])\n",
    "                if s[i:i + k] == s[i + k:i + k + k]:\n",
    "                    res = max(res, dfs(i + k, j) + 1)\n",
    "            return res\n",
    "        return dfs(0, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i >= n:\n",
    "                return 0\n",
    "            res = 1\n",
    "            for j in range(i + 1, i + (n - i) // 2 + 1):\n",
    "                if s[i:j] == s[j:j + j - i]:\n",
    "                    res = max(res, 1 + dfs(j))\n",
    "            return res\n",
    "        n = len(s)\n",
    "        ans = dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        @cache\n",
    "        def dfs(i) :\n",
    "            if i == len(s) :\n",
    "                return 0\n",
    "            l = len(s) - i + 1\n",
    "            res = 1\n",
    "            for j in range(i + 1, (i + l // 2) + 1) :\n",
    "                if s[i:j] == s[j:j + j - i] :\n",
    "                    res = max(res, dfs(j) + 1)\n",
    "            return res\n",
    "        return dfs(0)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i >= l:\n",
    "                return 0\n",
    "            ans = 1\n",
    "            for j in range(i + 1, i + (l - i) // 2 + 1):\n",
    "                if s[i:j] == s[j:j + j - i]:\n",
    "                    ans = max(ans, 1 + dfs(j))\n",
    "            return ans\n",
    "        l = len(s)\n",
    "        ans = dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i >= l:\n",
    "                return 0\n",
    "            ans = 1\n",
    "            for j in range(i + 1, i + (l - i) // 2 + 1):\n",
    "                if s[i:j] == s[j:j + j - i]:\n",
    "                    ans = max(ans, 1 + dfs(j))\n",
    "            return ans\n",
    "        \n",
    "        l = len(s)\n",
    "        ans = dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            res = 1\n",
    "            for k in range(1,(n-i)//2+1):\n",
    "                if s[i:i+k]==s[i+k:i+2*k]:\n",
    "                    res = max(res,1+dfs(i+k))\n",
    "            return res\n",
    "\n",
    "        n = len(s)\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            res = 1\n",
    "            for k in range(1, (n - 1 - i + 1) // 2 + 1):\n",
    "                if s[i:i + k] == s[i + k:i + k + k]:\n",
    "                    res = max(res, dfs(i + k) + 1)\n",
    "            return res\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "      \n",
    "        n = len(s)\n",
    "        @cache\n",
    "        def dp(i):\n",
    "            if i == len(s): # 递归出口，如果整个字符串都被删完了，那么就返回0，因为此时不能再进行删除了\n",
    "                return 0 \n",
    "            res = 1 # res初值设为1，是因为我最少都需要一次删除的操作，才能把整个字符串删完\n",
    "            for j in range(i+1, n):\n",
    "                t = j - i # t表示要删除的长度\n",
    "                if i + 2 * t > n: break \n",
    "                if s[i:i+t] == s[i+t:i+2*t]: # 如果删除的操作合法\n",
    "                    res = max(res, 1 + dp(i+t)) # 更新最大值，1+dp[i+t]，表示当前的删除操作次数1，和后续字符串操作次数的和\n",
    "            return res\n",
    "        return dp(0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "\n",
    "\n",
    "        n = len(s)\n",
    "        @lru_cache(None)\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            res = 1\n",
    "            rest = n-i\n",
    "            for x in range(1, rest//2+1):\n",
    "                if s[i:i+x] == s[i+x:i+2*x]:\n",
    "                    cur = dfs(i+x) + 1\n",
    "                    if cur > res:\n",
    "                        res = cur\n",
    "            return res\n",
    "\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "import sys\n",
    "\n",
    "sys.setrecursionlimit(5000)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        if len(set(s)) == 1:\n",
    "            return len(s)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(s):\n",
    "            ret = 1\n",
    "            for i in range(1, len(s) // 2 + 1):\n",
    "                if s[:i] == s[i:2 * i]:\n",
    "                    ret = max(ret, 1 + dfs(s[i:]))\n",
    "            return ret\n",
    "\n",
    "        rst = dfs(s)\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if len(set(s)) == 1: return n  # 特判全部相同的情况\n",
    "        lcp = [[0] * (n + 1) for _ in range(n + 1)]  # lcp[i][j] 表示 s[i:] 和 s[j:] 的最长公共前缀\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, i, -1):\n",
    "                if s[i] == s[j]:\n",
    "                    lcp[i][j] = lcp[i + 1][j + 1] + 1\n",
    "        f = [0] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(1, (n - i) // 2 + 1):\n",
    "                if lcp[i][i + j] >= j:  # 说明 s[i:i+j] == s[i+j:i+2*j]\n",
    "                    f[i] = max(f[i], f[i + j])\n",
    "            f[i] += 1\n",
    "        return f[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if len(set(s)) == 1: return n  # 特判全部相同的情况\n",
    "        lcp = [[0] * (n + 1) for _ in range(n + 1)]  # lcp[i][j] 表示 s[i:] 和 s[j:] 的最长公共前缀\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, i, -1):\n",
    "                if s[i] == s[j]:\n",
    "                    lcp[i][j] = lcp[i + 1][j + 1] + 1\n",
    "        f = [0] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(1, (n - i) // 2 + 1):\n",
    "                if lcp[i][i + j] >= j:  # 说明 s[i:i+j] == s[i+j:i+2*j]\n",
    "                    f[i] = max(f[i], f[i + j])\n",
    "            f[i] += 1\n",
    "        return f[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        if len(set(s))==1:return n\n",
    "        def lcp(s):\n",
    "            n = len(s)\n",
    "            lcp = [[0] * (n + 1) for _ in range(n + 1)]  # lcp[i][j] 表示 s[i:] 和 s[j:] 的最长公共前缀\n",
    "            for i in range(n - 1, -1, -1):\n",
    "                for j in range(n - 1, i, -1):\n",
    "                    lcp[i][j] = lcp[i + 1][j + 1] + 1 if s[i] == s[j] else 0\n",
    "            return lcp\n",
    "        lp=lcp(s)\n",
    "        f=[0]*n\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(1,(n-i)//2+1):\n",
    "                if lp[i][i+j]>=j:\n",
    "                    f[i]=max(f[i],f[i+j])\n",
    "            f[i]+=1\n",
    "        return f[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if len(set(s)) == 1: return n \n",
    "        lcp = [[0] * (n + 1) for _ in range(n + 1)]  # lcp[i][j] 表示 s[i:] 和 s[j:] 的最长公共前缀\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, i, -1):\n",
    "                if s[i] == s[j]:\n",
    "                    lcp[i][j] = lcp[i + 1][j + 1] + 1\n",
    "        f = [0] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(1, (n - i) // 2 + 1):\n",
    "                if lcp[i][i + j] >= j:  # 说明 s[i:i+j] == s[i+j:i+2*j]\n",
    "                    f[i] = max(f[i], f[i + j])\n",
    "            f[i] += 1\n",
    "        return f[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if min(s) == max(s):\n",
    "            return n\n",
    "        lcp = [[0] * (n + 1) for _ in range(n + 1)]  # lcp[i][j] 表示 s[i:] 和 s[j:] 的最长公共前缀\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, i, -1):\n",
    "                if s[i] == s[j]:\n",
    "                    lcp[i][j] = lcp[i + 1][j + 1] + 1\n",
    "        f = [0] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(1, (n - i) // 2 + 1):\n",
    "                if lcp[i][i + j] >= j:  # 说明 s[i:i+j] == s[i+j:i+2*j]\n",
    "                    f[i] = max(f[i], f[i + j])\n",
    "            f[i] += 1\n",
    "        return f[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if len(set(s)) == 1: return n  # 特判全部相同的情况\n",
    "        lcp = [[0] * (n + 1) for _ in range(n + 1)]  # lcp[i][j] 表示 s[i:] 和 s[j:] 的最长公共前缀\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, i, -1):\n",
    "                if s[i] == s[j]:\n",
    "                    lcp[i][j] = lcp[i + 1][j + 1] + 1\n",
    "        f = [0] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(1, (n - i) // 2 + 1):\n",
    "                if lcp[i][i + j] >= j:  # 说明 s[i:i+j] == s[i+j:i+2*j]\n",
    "                    f[i] = max(f[i], f[i + j])\n",
    "            f[i] += 1\n",
    "        return f[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if len(set(s)) == 1: return n  # 特判全部相同的情况\n",
    "        lcp = [[0] * (n + 1) for _ in range(n + 1)]  # lcp[i][j] 表示 s[i:] 和 s[j:] 的最长公共前缀\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, i, -1):\n",
    "                if s[i] == s[j]:\n",
    "                    lcp[i][j] = lcp[i + 1][j + 1] + 1\n",
    "        f = [0] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(1, (n - i) // 2 + 1):\n",
    "                if lcp[i][i + j] >= j:  # 说明 s[i:i+j] == s[i+j:i+2*j]\n",
    "                    f[i] = max(f[i], f[i + j])\n",
    "            f[i] += 1\n",
    "        return f[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        #这题涉及的知识点:\n",
    "        #1：求最长公共前缀，可以帮忙判断是否从某字符串某位置开始，后面有两段连续的子串,利用dp解决，然后看公共的长度即可\n",
    "        #2：这题从前往后看不好看，要从后往前看(从前往后会面临删除是在前缀的问题)\n",
    "        #定义f[i]表示删除s[i:]所需要的最大操作数(闭区间),f[i]=f[i+j]+1 if s[i:i+j]和s[i+j,i+2j]相同,然后在这么多之间选最大的（如果不存在相同的就是1）\n",
    "        #dp[i][j]表示s[i:]和s[j:]的最长公共前缀,dp[i][j]=dp[i+1][j+1]+1 if s[i]==s[j] else 0\n",
    "        size=len(s)\n",
    "        dp=[[0]*(size+1) for i in range(size+1)]\n",
    "        if len(set(s))==1:\n",
    "            return len(s)\n",
    "        for i in range(size-1,-1,-1):\n",
    "            for j in range(size-1,i,-1):\n",
    "                #这里i==size-1，j==size为烧饼，表示空串和一个字母的，公共自动是0，方便转移，因此不需要边界了\n",
    "                if s[i]==s[j]:\n",
    "                    dp[i][j]=dp[i+1][j+1]+1\n",
    "        f=[1 for i in range(size)]\n",
    "        for i in range(size-1,-1,-1):\n",
    "            for j in range(i+1,size):\n",
    "                if dp[i][j]>=j-i:\n",
    "                    f[i]=max(f[i],f[j]+1)\n",
    "        return f[0]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if len(set(s)) == 1: return n \n",
    "        lcp = [[0] * (n+1) for _ in range(n+1)]\n",
    "\n",
    "        for i in range(n-2, -1, -1):\n",
    "            for j in range(n-1, i, -1):\n",
    "                lcp[i][j] = 1 + lcp[i+1][j+1] if s[i] == s[j] else 0\n",
    "\n",
    "        #print(lcp)\n",
    "        dp = [0] * n \n",
    "        dp[n-1] = 1\n",
    "        for i in range(n-2, -1, -1):\n",
    "            dp[i] = 1\n",
    "            for j in range(i+1, n):\n",
    "                if j - i > (n -i) // 2:\n",
    "                    break \n",
    "                if lcp[i][j] >= j - i:\n",
    "                    dp[i] = max(dp[i], dp[j] + 1)\n",
    "        \n",
    "        return dp[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        \n",
    "        n = len(s)\n",
    "        if len(set(s)) == 1: return n # 全部相同 \n",
    "        lcp = [[0] * (n + 1) for _ in range(n + 1)] # lcp[i][j]表示s[i:] 和 s[j:]的最长公共前缀\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, i, -1):\n",
    "                if s[i] == s[j]:\n",
    "                    lcp[i][j] = lcp[i + 1][j + 1] + 1\n",
    "\n",
    "        f = [0] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(1, (n - i) // 2 + 1):\n",
    "                if lcp[i][i + j] >= j: # 说明s[i:i + j] == s[i + j: i + j * 2]\n",
    "                    f[i] = max(f[i], f[i + j])\n",
    "            f[i] += 1\n",
    "        return f[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if len(set(s)) == 1: \n",
    "            return n  # 特判全部相同的情况\n",
    "        lcp = [[0] * (n + 1) for _ in range(n + 1)]  # lcp[i][j] 表示 s[i:] 和 s[j:] 的最长公共前缀\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, i, -1):\n",
    "                if s[i] == s[j]:\n",
    "                    lcp[i][j] = lcp[i + 1][j + 1] + 1\n",
    "        f = [0] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(1, (n - i) // 2 + 1):\n",
    "                if lcp[i][i + j] >= j:  # 说明 s[i:i+j] == s[i+j:i+2*j]\n",
    "                    f[i] = max(f[i], f[i + j])\n",
    "            f[i] += 1\n",
    "        return f[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if len(set(s)) == 1: return n  # 特判全部相同的情况\n",
    "        lcp = [[0] * (n + 1) for _ in range(n + 1)]  # lcp[i][j] 表示 s[i:] 和 s[j:] 的最长公共前缀\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, i, -1):\n",
    "                if s[i] == s[j]:\n",
    "                    lcp[i][j] = lcp[i + 1][j + 1] + 1\n",
    "        f = [0] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(1, (n - i) // 2 + 1):\n",
    "                if lcp[i][i + j] >= j:  # 说明 s[i:i+j] == s[i+j:i+2*j]\n",
    "                    f[i] = max(f[i], f[i + j])\n",
    "            f[i] += 1\n",
    "        return f[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if len(set(s)) == 1: return n  # 特判全部相同的情况\n",
    "        lcp = [[0] * (n + 1) for _ in range(n + 1)]  # lcp[i][j] 表示 s[i:] 和 s[j:] 的最长公共前缀\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, i, -1):\n",
    "                if s[i] == s[j]:\n",
    "                    lcp[i][j] = lcp[i + 1][j + 1] + 1\n",
    "        f = [0] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(1, (n - i) // 2 + 1):\n",
    "                if lcp[i][i + j] >= j:  # 说明 s[i:i+j] == s[i+j:i+2*j]\n",
    "                    f[i] = max(f[i], f[i + j])\n",
    "            f[i] += 1\n",
    "        return f[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if len(set(s)) == 1: return n  # 特判全部相同的情况\n",
    "        lcp = [[0] * (n + 1) for _ in range(n + 1)]  # lcp[i][j] 表示 s[i:] 和 s[j:] 的最长公共前缀\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, i, -1):\n",
    "                if s[i] == s[j]:\n",
    "                    lcp[i][j] = lcp[i + 1][j + 1] + 1\n",
    "        f = [0] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(1, (n - i) // 2 + 1):\n",
    "                if lcp[i][i + j] >= j:  # 说明 s[i:i+j] == s[i+j:i+2*j]\n",
    "                    f[i] = max(f[i], f[i + j])\n",
    "            f[i] += 1\n",
    "        return f[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "\n",
    "        @lru_cache(maxsize=None)\n",
    "        def dfs(i):\n",
    "            if i >= len(s):\n",
    "                return 0\n",
    "            result = 1\n",
    "            for j in range(i+1, i+(len(s)-i)//2+1):\n",
    "                if s[i:j] == s[j:j+j-i]:\n",
    "                    result = max(result, 1+dfs(j))\n",
    "            return result\n",
    "        \n",
    "        # return dfs(0)\n",
    "        n = len(s)\n",
    "        if len(set(s)) == 1:\n",
    "            return n\n",
    "        lcp = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, i, -1):\n",
    "                if s[i] == s[j]:\n",
    "                    lcp[i][j] = lcp[i + 1][j + 1] + 1\n",
    "        dp = [0] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(1, (n - i) // 2 + 1):\n",
    "                if lcp[i][i + j] >= j:\n",
    "                    dp[i] = max(dp[i], dp[i+j])\n",
    "            dp[i] += 1\n",
    "        return dp[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if len(set(s)) == 1: return n\n",
    "        lcp = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(n-1,i,-1):\n",
    "                if s[i] == s[j]:\n",
    "                    lcp[i][j] = lcp[i+1][j+1] + 1\n",
    "        f = [0] * n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(1, (n-i) // 2 + 1):\n",
    "                if lcp[i][i+j] >= j:\n",
    "                    f[i] = max(f[i], f[i+j])\n",
    "            f[i] += 1\n",
    "        return f[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "        if len(set(s))==1: \n",
    "            return n\n",
    "        \n",
    "        lcp = [[0]*(n+1) for _ in range(n+1)]\n",
    "\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(n-1,i,-1):\n",
    "                if s[i]==s[j]:\n",
    "                    lcp[i][j] = lcp[i+1][j+1]+1\n",
    "        \n",
    "        dp = [0]*n\n",
    "\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(i+1,n):\n",
    "                if lcp[i][j]>=j-i:\n",
    "                    dp[i] = max(dp[i],dp[j]+1)\n",
    "            dp[i] = max(1,dp[i])\n",
    "\n",
    "        return dp[0]\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if len(set(s)) == 1: return n  # 特判全部相同的情况\n",
    "        lcp = [[0] * (n + 1) for _ in range(n + 1)]  # lcp[i][j] 表示 s[i:] 和 s[j:] 的最长公共前缀\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, i, -1):\n",
    "                if s[i] == s[j]:\n",
    "                    lcp[i][j] = lcp[i + 1][j + 1] + 1\n",
    "        f = [0] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(1, (n - i) // 2 + 1):\n",
    "                if lcp[i][i + j] >= j:  # 说明 s[i:i+j] == s[i+j:i+2*j]\n",
    "                    f[i] = max(f[i], f[i + j])\n",
    "            f[i] += 1\n",
    "        return f[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        # 定义f[i]表示删除后缀s[i:]所需要的最大操作数\n",
    "        n = len(s)\n",
    "        if len(set(s)) == 1: return len(s)\n",
    "        lcp = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, i, -1):\n",
    "                if s[i] == s[j]:\n",
    "                    lcp[i][j] = lcp[i + 1][j + 1] + 1\n",
    "        f = [0] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(1, (n - i) // 2 + 1):\n",
    "                if lcp[i][i + j] >= j:\n",
    "                    f[i] = max(f[i], f[i + j])\n",
    "            f[i] += 1\n",
    "        return f[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if len(set(s)) == 1:\n",
    "            return n\n",
    "        dp = [[0]*(n+1) for _ in range(n+1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(n-1,i,-1):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i + 1][j + 1] + 1\n",
    "        f = [0] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(1, (n - i) // 2 + 1):\n",
    "                if dp[i][i + j] >= j:  # 说明 s[i:i+j] == s[i+j:i+2*j]\n",
    "                    f[i] = max(f[i], f[i + j])\n",
    "            f[i] += 1\n",
    "        return f[0]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s):\n",
    "        n = len(s)\n",
    "        if (len(set(s)) == 1): return n\n",
    "        lcs = [[0] * (n + 1) for i in range(n + 1)]\n",
    "        dp = [1] * n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(i + 1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    lcs[i][j] = lcs[i + 1][j + 1] + 1\n",
    "                if lcs[i][j] >= j - i:\n",
    "                    dp[i] = max(dp[i], dp[j] + 1)\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "\n",
    "        @lru_cache(maxsize=None)\n",
    "        def dfs(i):\n",
    "            if i >= len(s):\n",
    "                return 0\n",
    "            result = 1\n",
    "            for j in range(i+1, i+(len(s)-i)//2+1):\n",
    "                if s[i:j] == s[j:j+j-i]:\n",
    "                    result = max(result, 1+dfs(j))\n",
    "            return result\n",
    "        \n",
    "        # return dfs(0)\n",
    "        n = len(s)\n",
    "        if len(set(s)) == 1:\n",
    "            return n\n",
    "        lcp = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, i, -1):\n",
    "                if s[i] == s[j]:\n",
    "                    lcp[i][j] = lcp[i + 1][j + 1] + 1\n",
    "        dp = [0] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(1, (n - i) // 2 + 1):\n",
    "                if lcp[i][i + j] >= j:\n",
    "                    dp[i] = max(dp[i], dp[i+j])\n",
    "            dp[i] += 1\n",
    "        return dp[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if len(set(s)) == 1: return n  # 特判全部相同的情况\n",
    "        lcp = [[0] * (n + 1) for _ in range(n + 1)]  # lcp[i][j] 表示 s[i:] 和 s[j:] 的最长公共前缀\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(i + 1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    lcp[i][j] = lcp[i + 1][j + 1] + 1\n",
    "        f = [0] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(1, (n - i) // 2 + 1):\n",
    "                if lcp[i][i + j] >= j:  # 说明 s[i:i+j] == s[i+j:i+2*j]\n",
    "                    f[i] = max(f[i], f[i + j])\n",
    "            f[i] += 1\n",
    "        return f[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "\n",
    "        @lru_cache(maxsize=None)\n",
    "        def dfs(i):\n",
    "            if i >= len(s):\n",
    "                return 0\n",
    "            result = 1\n",
    "            for j in range(i+1, i+(len(s)-i)//2+1):\n",
    "                if s[i:j] == s[j:j+j-i]:\n",
    "                    result = max(result, 1+dfs(j))\n",
    "            return result\n",
    "        \n",
    "        # return dfs(0)\n",
    "        n = len(s)\n",
    "        if len(set(s)) == 1:\n",
    "            return n\n",
    "        lcp = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, i, -1):\n",
    "                if s[i] == s[j]:\n",
    "                    lcp[i][j] = lcp[i + 1][j + 1] + 1\n",
    "        dp = [0] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            dp[i] = 1\n",
    "            for j in range(1, (n - i) // 2 + 1):\n",
    "                if lcp[i][i + j] >= j:\n",
    "                    dp[i] = max(dp[i], 1+dp[i+j])\n",
    "                    is_handle = True  \n",
    "        return dp[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if len(set(s)) == 1: return n  # 特判全部相同的情况\n",
    "        lcp = [[0] * (n + 1) for _ in range(n + 1)]  # lcp[i][j] 表示 s[i:] 和 s[j:] 的最长公共前缀\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, i, -1):\n",
    "                if s[i] == s[j]:\n",
    "                    lcp[i][j] = lcp[i + 1][j + 1] + 1\n",
    "        f = [0] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(1, (n - i) // 2 + 1):\n",
    "                if lcp[i][i + j] >= j:  # 说明 s[i:i+j] == s[i+j:i+2*j]\n",
    "                    f[i] = max(f[i], f[i + j])\n",
    "            f[i] += 1\n",
    "        return f[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if len(set(s)) == 1 : return n\n",
    "        lcp = [[0]*(n+1)for _ in range (n+1)]#二维数组\n",
    "        for i in range (n-1,-1,-1):\n",
    "            for j in range (n-1,i ,-1):\n",
    "                if s[i] == s[j]:\n",
    "                    lcp[i][j]=lcp[i+1][j+1]+1\n",
    "                else :\n",
    "                    lcp[i][j]=0\n",
    "        f = [0]*n\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(1,(n-i)//2+1):\n",
    "                if lcp[i][i+j]>=j:\n",
    "                    f[i] = max(f[i],f[i+j])\n",
    "            f[i]+=1\n",
    "        return f[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if len(set(s)) == 1: return len(s)\n",
    "        lcp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, i, -1):\n",
    "                if s[i] == s[j]:\n",
    "                    lcp[i][j] = lcp[i + 1][j + 1] + 1\n",
    "        f = [0 for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(1, (n - i) // 2 + 1):\n",
    "                if lcp[i][i+j] >= j:\n",
    "                    f[i] = max(f[i], f[i + j])\n",
    "            f[i] += 1\n",
    "        return f[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if len(set(s)) == 1: return n\n",
    "\n",
    "        lcp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]\n",
    "        for i in range(n -1, -1, -1):\n",
    "            for j in range(n - 1, i, -1):\n",
    "                if s[i] == s[j]:\n",
    "                    lcp[i][j] = lcp[i + 1][j + 1] + 1\n",
    "        \n",
    "        dp = [0 for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            maxv = 0\n",
    "            for j in range(i, i + (n - i) // 2):\n",
    "                if lcp[i][j + 1] >= (j - i + 1):\n",
    "                    maxv = max(dp[j + 1], maxv)\n",
    "            dp[i] = maxv + 1\n",
    "            \n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        if len(set(s)) == 1: return n  # 特判全部相同的情况\n",
    "        lcp=[[0 for _ in range(n+1)] for _ in range(n+1)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(n-1, i, -1):\n",
    "                if s[i]==s[j]:\n",
    "                    lcp[i][j]=lcp[i+1][j+1]+1\n",
    "\n",
    "        dp=[0]*n\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(1,(n-i)//2+1):\n",
    "                if lcp[i][i+j]>=j:\n",
    "                    dp[i]=max(dp[i], dp[i+j])\n",
    "            dp[i]+=1\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteString(self, s: str) -> int:\n",
    "        \n",
    "        n = len(s)\n",
    "        if len(set(s)) == 1:\n",
    "            return n\n",
    "        lcp = [[0 for _ in range(n+1)] for _ in range(n+1)]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(n-1,i,-1):\n",
    "                lcp[i][j] = lcp[i+1][j+1] + 1 if s[i] == s[j] else 0\n",
    "\n",
    "        dp = [1] * (n + 1)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(n-1,i,-1):\n",
    "                if lcp[i][j] >= j - i:\n",
    "                    dp[i] = max(dp[i],dp[j] + 1)\n",
    "        return dp[0]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
